package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

public class No112路径总和 {

    /**
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例: 
     * 给定如下二叉树，以及目标和 sum = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \      \
     *         7    2      1
     * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
     */

    //注意叶子节点这个概念,必须是最后的节点
    public static boolean hasPathSum(TreeNode root, int sum) {
        return dg(root,sum);
    }

    private static boolean dg(TreeNode root,int sum){
        if(root==null)
            return false;
        if(root.left==null&&root.right==null)
            return sum==root.val;//还没减呢

        boolean flag1 = dg(root.left, sum - root.val);
        if(flag1)//快捷
            return true;

        boolean flag2 = dg(root.right, sum - root.val);
        if(flag2)
            return true;

        return false;
    }

    public static boolean hasPathSum2(TreeNode root,int sum){
        if(root==null)
            return false;
        Queue<TreeNode> queue=new LinkedList<>();
        Queue<Integer> valQueue=new LinkedList<>();
        queue.add(root);
        valQueue.add(sum);
        while (!queue.isEmpty()){
            Integer currentVal=valQueue.poll();
            TreeNode poll = queue.poll();
            currentVal -= poll.val;
            if (poll.left == null && poll.right == null && currentVal == 0)//必须是最底层节点
                return true;
            if (poll.left != null) {
                queue.add(poll.left);
                valQueue.add(currentVal);
            }
            if (poll.right != null) {
                queue.add(poll.right);
                valQueue.add(currentVal);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1});
        boolean b = hasPathSum2(nodeByArr, 22);
        System.out.println(b);
    }


}
